package com.algorithm.ch1.cjm.design;

import java.util.Arrays;
import java.util.Stack;

/**
 * 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
 * <p>
 * push(x) -- 将元素 x 推入栈中。
 * pop() -- 删除栈顶的元素。
 * top() -- 获取栈顶元素。
 * getMin() -- 检索栈中的最小元素。
 *
 * @Author: Jie Ming Chen
 * @Date: 2018/9/12
 * @Version 1.0
 */
public class MinStack {

    /**
     * 栈容量
     */
    private Integer[] data = null;

    /**
     * 栈顶指针
     */
    private int top = -1;

    private int min = Integer.MAX_VALUE;

    Stack<Integer> stack;

    /**
     * 初始化数据结构
     */
    public MinStack() {

        data = new Integer[1000];
    }

    public void push(int x) {

        int length = data.length;
        if ( top >= length - 1 ) {

            Integer[] arr1 = new Integer[ length + 1000];
            int index = 0;
            while (index < length) {
                arr1[index] = data[index];
            }
            data = arr1;
        }

        data[++top] = x;

        if (min > x) {
            min = x;
        }
    }

    public void pop() {

        if (top < 0) {
            return;
        }

        if (data[top].equals(min)) {
            int index = 0;
            min = Integer.MAX_VALUE;
            while (index < top) {
                if (min > data[index]) {
                    min = data[index];
                }
                index++;
            }
        }

        data[top] = null;
        top--;
    }

    public int top() {

        if (top < 0) {
            return 0;
        }

        return data[top];
    }

    public int getMin() {

        if (top < 0) {
            return 0;
        }

        return min;
    }

    public static void main(String[] args) {

        MinStack minStack = new MinStack();
        minStack.push(2147483646);
        minStack.push(2147483646);
        minStack.push(2147483647);

        System.out.println(minStack.top());

        minStack.pop();
        System.out.println(Arrays.toString(minStack.data));

        System.out.println(minStack.getMin());

        minStack.top();
        System.out.println(minStack.top());

        System.out.println(Integer.MIN_VALUE);
    }

}
